package java;

public class Question4 {
    public static void main(String[] args) {
        int[] num1 = {};
        int[] num2 = {2,3};
        System.out.println(findMedianSortedArrays(num1,num2));
    }
    public static double findMedianSortedArrays(int[] nums1, int[] nums2) {
        if(nums1 == null || nums1.length < 1){
            return findMedian(nums2);
        }else {
            if (nums2 == null || nums2.length < 1){
                return findMedian(nums1);
            }else {
                if ((nums1.length + nums2.length)%2 ==0){
                    return (findMedian(nums2) + findMedian(nums1)) / 2;
                }else {
                    return findMedianOld(nums1,nums2);
                }
            }
        }

    }

    private static double findMedianOld(int[] nums1, int[] nums2) {
        if (nums1.length > nums2.length){
            int[] temp = nums1;
            nums1 = nums2;
            nums2 = temp;
        }
        int iIndex;
        int jIndex;
        int m = nums1.length;
        int n = nums2.length;
        int halfLength = (m + n + 1) / 2;
        int iMin = 0;
        int iMax = nums1.length;
        while (iMin <= iMax){
            iIndex = (iMax + iMin)/2;
            jIndex = halfLength - iIndex;
            if (iIndex > iMin && nums1[iIndex - 1] > nums2[jIndex]){
                iMax = iIndex - 1;
            }else if (iIndex < iMax && nums1[iIndex] < nums2[jIndex - 1]){
                iMin = iIndex + 1;
            }else {
                int maxLeft = 0;
                if (iIndex == 0) {
                    maxLeft = nums2[jIndex-1];
                } else if (jIndex == 0) {
                    maxLeft = nums1[iIndex-1];
                } else {
                    maxLeft = Math.max(nums1[iIndex-1], nums2[jIndex-1]);
                }
                if ( (m + n) % 2 == 1 ) {
                    return maxLeft;
                }

                int minRight = 0;
                if (iIndex == m) {
                    minRight = nums2[jIndex];
                } else if (jIndex == n) {
                    minRight = nums1[iIndex];
                } else {
                    minRight = Math.min(nums2[jIndex], nums1[iIndex]);
                }


                return (maxLeft + minRight) / 2.0;
            }
        }
        return 0.0;
    }

    private static double findMedian(int[] nums) {
        int index = nums.length/2;
        if (nums.length % 2 == 0){
            return (double) (nums[index] + nums[index - 1]) / 2;
        }else {
            return (double) nums[index];
        }

    }
//    public double findMedianSortedArrays1(int[] A, int[] B) {
//        int m = A.length;
//        int n = B.length;
//        if (m > n) { // to ensure m<=n
//            int[] temp = A; A = B; B = temp;
//            int tmp = m; m = n; n = tmp;
//        }
//
//        int iMin = 0, iMax = m, halfLen = (m + n + 1) / 2;
//
//        while (iMin <= iMax) {
//            int i = (iMin + iMax) / 2;
//            int j = halfLen - i;
//
//            if (i < iMax && B[j-1] > A[i]){
//                iMin = i + 1; // i is too small
//            }
//            else if (i > iMin && A[i-1] > B[j]) {
//                iMax = i - 1; // i is too big
//            }
//            else { // i is perfect
//                int maxLeft = 0;
//                if (i == 0) { maxLeft = B[j-1]; }
//                else if (j == 0) { maxLeft = A[i-1]; }
//                else { maxLeft = Math.max(A[i-1], B[j-1]); }
//                if ( (m + n) % 2 == 1 ) { return maxLeft; }
//
//                int minRight = 0;
//                if (i == m) { minRight = B[j]; }
//                else if (j == n) { minRight = A[i]; }
//                else { minRight = Math.min(B[j], A[i]); }
//
//                return (maxLeft + minRight) / 2.0;
//            }
//        }
//        return 0.0;
//    }
}
